A barrel shifter is an electronic circuit which shifts a digital data word by a certain number of bits in a cyclic manner, wrapping bits around as they are shifted past the end of the data word. For example, a data word with bits ABCDEF, where the letters represent bit positions rather than bit values, when shifted two bits to the right in a barrel shifter, becomes EFABCD.
Barrel shifters are used in a number of different types of electronic circuits, such as storage systems, cellular telephone systems, and radio transmission systems. For example, a barrel shifter may be used in a Low Density Parity Check (LDPC) layer decoder. An LDPC code is a parity-based code that can be visually represented in a Tanner graph 100 as illustrated in FIG. 1. In an LDPC decoder, multiple parity checks are performed in a number of check nodes 102, 104, 106 and 108 for a group of variable nodes 110, 112, 114, 116, 118, 120, 122, and 124. The connections (or edges) between variable nodes 110-124 and check nodes 102-108 are selected as the LDPC code is designed, balancing the strength of the code against the complexity of the decoder required to execute the LDPC code as data is obtained. The number and placement of parity bits in the group are selected as the LDPC code is designed. Messages are passed between connected variable nodes 110-124 and check nodes 102-108 in an iterative process, passing beliefs about the values that should appear in variable nodes 110-124 to connected check nodes 102-108. Parity checks are performed in the check nodes 102-108 based on the messages and the results are returned to connected variable nodes 110-124 to update the beliefs if necessary. LDPC decoders may be implemented in binary or non-binary fashion. In a binary LDPC decoder, variable nodes 110-124 contain scalar values based on a group of data and parity bits that are retrieved from a storage device, received by a transmission system or obtained in some other way. Messages in the binary LDPC decoders are scalar values transmitted as plain-likelihood probability values or log-likelihood-ratio (LLR) values representing the probability that the sending variable node contains a particular value. In a non-binary LDPC decoder, variable nodes 110-124 contain symbols from a Galois Field, a finite field GF(pk) that contains a finite number of elements, characterized by size pk where p is a prime number and k is a positive integer. Messages in the non-binary LDPC decoders are multi-dimensional vectors, generally either plain-likelihood probability vectors or LLR vectors.
The connections between variable nodes 110-124 and check nodes 102-108 may be presented in matrix form as follows, where columns represent variable nodes, rows represent check nodes, and a random non-zero element a(i,j) from the Galois Field at the intersection of a variable node column and a check node row indicates a connection between that variable node and check node and provides a permutation for messages between that variable node and check node:
  H  =      [                                        a            ⁡                          (                              1                ,                1                            )                                                0                          0                                      a            ⁡                          (                              1                ,                2                            )                                                0                                      a            ⁡                          (                              1                ,                3                            )                                                            a            ⁡                          (                              1                ,                4                            )                                                0                                      0                                      a            ⁡                          (                              2                ,                1                            )                                                0                          0                                      a            ⁡                          (                              2                ,                2                            )                                                0                          0                                      a            ⁡                          (                              2                ,                3                            )                                                                        a            ⁡                          (                              3                ,                1                            )                                                0                                      a            ⁡                          (                              3                ,                2                            )                                                0                                      a            ⁡                          (                              3                ,                3                            )                                                            a            ⁡                          (                              3                ,                4                            )                                                0                                      a            ⁡                          (                              3                ,                5                            )                                                            0                                      a            ⁡                          (                              4                ,                1                            )                                                0                                      a            ⁡                          (                              4                ,                2                            )                                                0                          0                                      a            ⁡                          (                              4                ,                3                            )                                                            a            ⁡                          (                              4                ,                4                            )                                            ]  
By providing multiple check nodes 102-108 for the group of variable nodes 110-124, redundancy in error checking is provided, enabling errors to be corrected as well as detected. Each check node 102-108 performs a parity check on bits or symbols passed as messages from its neighboring (or connected) variable nodes. In the example LDPC code corresponding to the Tanner graph 100 of FIG. 1, check node 102 checks the parity of variable nodes 110, 116, 120 and 122. Values are passed back and forth between connected variable nodes 110-124 and check nodes 102-108 in an iterative process until the LDPC code converges on a value for the group of data and parity bits in the variable nodes 110-124. For example, variable node 110 passes messages to check nodes 102 and 106. Check node 102 passes messages back to variable nodes 110, 116, 120 and 122. The messages between variable nodes 110-124 and check nodes 102-108 are probabilities or beliefs, thus the LDPC decoding algorithm is also referred to as a belief propagation algorithm. Each message from a node represents the probability that a bit or symbol has a certain value based on the current value of the node and on previous messages to the node.
A message from a variable node to any particular neighboring check node is computed using any of a number of algorithms based on the current value of the variable node and the last messages to the variable node from neighboring check nodes, except that the last message from that particular check node is omitted from the calculation to prevent positive feedback. Similarly, a message from a check node to any particular neighboring variable node is computed based on the current value of the check node and the last messages to the check node from neighboring variable nodes, except that the last message from that particular variable node is omitted from the calculation to prevent positive feedback. As iterations are performed in the system, messages pass back and forth between variable nodes 110-124 and check nodes 102-108, with the values in the nodes 102-124 being adjusted based on the messages that are passed, until the values converge and stop changing or until processing is halted.
In some applications, multiple barrel shifters are needed to process data words of different lengths. A need therefore remains for efficient barrel shifter architectures for processing data words of different lengths.